package com.exercises;


class Exercise45 {
    public static void main(String[] args) {
        System.out.println(new Exercise45().jump(new int[]{2, 3, 1, 1, 4}));
    }


    public int jump(int[] nums) {
        int length = nums.length;
        Integer[] step = new Integer[length];
        int max = 0;
        for (int i = 0; i < length; i++) {
            if (i == 0) {
                step[0] = 0;
            }
            int value = nums[i];
            if (value + i <= max) {
                continue;
            } else {
                for (int j = max; j <= i + value; j++) {
                    if (j < length) {
                        if (step[j] == null) {
                            step[j] = step[i] + 1;
                        } else {
                            step[j] = Math.min(step[i] + 1, step[j]);
                        }
                    }

                }
                max = Math.max(max, value + i);
            }

        }
        for (int i = 0; i < length; i++) {
            System.out.print(step[i]);
            System.out.print("  ");
        }
        return step[length - 1];
    }


}

